package recursion;

import LeetCodeP.ListNode;

/**
 * 给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。
 *你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
 *
 * 给定 1->2->3->4, 你应该返回 2->1->4->3.
 *
 * 首先，我们交换列表中的前两个节点，也就是 head 和 head.next；
 * 然后我们以 swap(head.next.next) 的形式调用函数自身，以交换头两个节点之后列表的其余部分。
 * 最后，我们将步骤（2）中的子列表的返回头与步骤（1）中交换的两个节点相连，以形成新的链表。
 *
 *
 * @author long
 * @date 2020-07-24 22:37
 */
class Solution {

    public ListNode swapPairs(ListNode head) {
        ListNode dummy=new ListNode(0);
        ListNode p=dummy;
        while (head!=null){
            if(head!=null&&head.next!=null){
                ListNode tmp=head.next;
                p.next=tmp;
                head.next=head.next.next;
                tmp.next=head;
                head=head.next;
                p=p.next.next;
            }else {
                p.next=head;
                head=head.next;

            }
        }
        return dummy.next;
    }

    public class ListNode {
     int val;
     ListNode next;
     ListNode(int x) { val = x; }
 }

}
